| | Category | CS | P03 | Optimizing the Deflation Strategy of a Divide and Conquer Eigensolver |
| | Abstract | A classic problem in numerical linear algebra is the calculation of the |
| | eigenvalues of a symmetric matrix. These eigenvalues are useful in |
| | calculating critical frequencies in many systems, such as vibrations in |
| | mass spring systems ([1] page 254). Not much research has been done |
| | on the deflating criteria in the divide and conquer eigenvalue algorithm. My |
| | hypothesis is that a better deflating criterion than the currently used |
| | constant threshold exists, and that the deflating threshold will be a |
| | function of the size of the matrix. A genetic algorithm is used to search for |
| | this better function. The genetic algorithm (GA) in 12 out of 18 runs (on |
| | 100 random matrices) showed that a logarithmic function is better than a |
| | constant function. A quadratic fit yielded a logarithmic deflating function |
| | that was optimal for general matrices, not just the 100 random matrices |
| | used in each run of the GA. Data collected with this new function showed |
| | acceptable errors (1.73 accurate digits versus the average 1.88 |
| | computed with the GA). With this function, the divide and conquer method |
| | yielded 2.61 accurate digits on larger matrices. In conclusion, the |
| | hypothesis was correct, and the new logarithmic deflating function is |
| | better than a constant function. |
| | Bibliography | [1] Demmel, James W. Applied Numerical Linear Algebra. 1 ed. Philadelphia: |
| | SIAM, |
| | 1997. Print. |
| | [2] Potter, Christopher. "A Parallel Divide and Conquer Eigensolver." EPFL |
| |
| | Supercomputing Review. EPFL, n.d. Web. 14 Feb. 2010. |
| | <http://ditwww.epfl.ch/SIC/SA/publications/SCR95/7-95-27a.html>. |
| | [3] Stewart, G. W. Matrix Algorithms, Volume II: Eigensystems. 1 ed. |
| | Philadelphia: |